package com.linyaonan.leetcode.medium._2962;

/**
 * 给你一个整数数组 nums 和一个 正整数 k 。
 *
 * 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
 *
 * 子数组是数组中的一个连续元素序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,3,2,3,3], k = 2
 * 输出：6
 * 解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
 * 示例 2：
 *
 * 输入：nums = [1,4,2,1], k = 3
 * 输出：0
 * 解释：没有子数组包含元素 4 至少 3 次。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^6
 * 1 <= k <= 10^5
 *
 * @author: Lin
 * @date: 2024/10/31
 */
public class CountSubarraysWhereMaxElementAppearsAtLeastKTimes {

    /**
     * 滑动窗口，找出最大值k
     * 左指针从0开始
     * @param nums
     * @param k
     * @return
     */
    public long countSubarrays(int[] nums, int k) {
        // 1. 找到最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(nums[i], max);
        }
        // 2. 滑动窗口进行统计
        int l = 0;
        int r = 0;
        int add = 0;
        long count = 0L;

        while (l <= r && r < nums.length) {
            int current = nums[r];
            if (current == max) {
                add++;
            }

            while (add == k) {
                count += (nums.length - r);
                int pre = nums[l];
                if (pre == max) {
                    add--;
                }
                l++;
            }

            r++;
        }

        return count;
    }

}
